//
// Description: 1314. 矩阵区域和
// Created by Loading on 2022/7/3.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k) {
    int m = mat.size();
    int n = mat[0].size();

    // 二维前缀和
    vector<vector<int>> pre(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }

    vector<vector<int>> res(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 拿到左上角和右下角的坐标
            int r1 = i - k < 0 ? 0 : i - k;
            int c1 = j - k < 0 ? 0 : j - k;
            int r2 = i + k >= m ? m - 1 : i + k;
            int c2 = j + k >= n ? n - 1 : j + k;
            res[i][j] = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
        }
    }

    return res;
}

int main() {
    vector<vector<int>> mat{{1, 2, 3},
                            {4, 5, 6},
                            {7, 8, 9}};
    int k = 1;

    auto res = matrixBlockSum(mat, k);

    for (const auto& v : res) {
        for (auto x : v) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}
